package ru.ifmo.cppsc.syntactic;


import ru.ifmo.cppsc.grammar.Symbol;
import ru.ifmo.cppsc.grammar.Grammar;
import ru.ifmo.cppsc.grammar.ProperGrammar;
import ru.ifmo.cppsc.grammar.Production;
import ru.ifmo.cppsc.workers.FileWorker;

import java.util.*;

/**
 * Author: Olga Komaleva
 * Date: Jun 15, 2008
 */
public class WeakPrecedenceAnalyse extends SyntacticAnalyse implements LRParser.TransactionFunctions {
    public String precedence[][];

    private HashMap<Symbol, HashMap<Symbol, String>> conflicts = new HashMap<Symbol, HashMap<Symbol, String>>();


    public WeakPrecedenceAnalyse(Grammar grammar) {
        super(grammar);
        precedence = new String[grammar.size()][grammar.size()];
        initPrecedence();

        int size = 0;
        for (Symbol a : conflicts.keySet()) {

            for (Symbol b : conflicts.get(a).keySet()) {
                System.out.println(a.getName() + " " + b.getName() + " " + conflicts.get(a).get(b));
                size++;
                if (!grammar.isTerminal(b) && grammar.isTerminal(a)) {
                    grammar.killNonTerminal(b);
                    //todo

                }
                if (b.getName().equals("Assign")) {
                    System.out.println("--------------------------------------------------");
                    assert false;
                }
            }
            if (!grammar.isTerminal(a)) {
                grammar.killNonTerminal(a);
            }
            if (a.getName().equals("Assign")) assert false;
        }
        System.out.println(size);
        if (size > 0) {
            //grammar.print();
            conflicts = new HashMap<Symbol, HashMap<Symbol, String>>();
            System.out.println("-------------");
            precedence = new String[grammar.size()][grammar.size()];
            initPrecedence();


            size = 0;
            for (Symbol a : conflicts.keySet()) {

                for (Symbol b : conflicts.get(a).keySet()) {
                    System.out.println(a.getName() + " " + b.getName() + "  " + conflicts.get(a).get(b));
                    size++;
                }
            }
            System.out.println(size);
            System.out.println("-------------");
        }
    }

    public void saveTable(String fileName) {
        FileWorker.saveTable(fileName, precedence);
    }

    public WeakPrecedenceAnalyse(ProperGrammar grammar, String fileName) {
        super(grammar);
        precedence = new String[grammar.size()][grammar.size()];
        FileWorker.readTable(fileName);
    }

    private void initPrecedence() {
        ArrayList<Symbol[]> set = getSetI();

        for (Symbol[] pair : set) {
            if (!grammar.isTerminal(pair[1])) {
                for (Production p : grammar.getProductions()) {
                    if (p.getLeft() == pair[1]) {
                        int i = pair[0].getId();

                        Symbol symbol = p.getRight()[0];
                        if (symbol != grammar.EPSILON) {
                            setLess(i, symbol.getId());

                           /* for (Symbol k : first[symbol.getId()]) { //???
                                setLess(i, k.getId());
                            }*/
                        }

                        for (Symbol[] pair1 : getBinarySubstrings(p.getRight())) {
                            setEq(pair1[0].getId(), pair1[1].getId());
                        }
                    }
                }
            }

            if (!grammar.isTerminal(pair[0])) {
                for (Production p : grammar.getProductions()) {
                    if (p.getLeft() == pair[0]) {
                        if (p.getRight()[p.getRight().length - 1] != grammar.EPSILON)
                            setGreat(p.getRight()[p.getRight().length - 1].getId(), pair[1].getId());
                    }
                }
            }
        }
    }

    private ArrayList<Symbol[]> getSetI() {
        ArrayList<Symbol[]> set = new ArrayList<Symbol[]>();

        set.add(new Symbol[]{grammar.getStart(), STOP_SYMBOL});
        set.add(new Symbol[]{STOP_SYMBOL, grammar.getStart()});

        for (int i = 0; i < set.size(); i++) {
            Symbol[] deltaSet = set.get(i);
            assert(deltaSet.length <= 2);

            assert(deltaSet.length == 2);


            for (int j = 0; j < 2; j++) {
                Symbol nonTerminal = deltaSet[j];
                if ((nonTerminal != grammar.EPSILON) && !grammar.isTerminal(nonTerminal)) {
                    for (Production p : grammar.getProductions()) {
                        if (p.getLeft() == nonTerminal) {

                            ArrayList<Symbol[]> binarySubSets = getBinarySubstrings(p.getRight());
                            if (j == 0) {
                                if (p.getRight()[p.getRight().length - 1] != grammar.EPSILON)
                                    binarySubSets.add(new Symbol[]{p.getRight()[p.getRight().length - 1], deltaSet[j + 1]});
                            } else {
                                if (p.getRight()[0] != grammar.EPSILON)
                                    binarySubSets.add(new Symbol[]{deltaSet[0], p.getRight()[0]});
                            }

                            for (Symbol[] pair : binarySubSets) {
                                if (!contains(set, pair)) {
                                    set.add(pair);
                                }
                            }
                        }
                    }
                }
            }
        }
        return set;
    }

    private ArrayList<Symbol[]> getBinarySubstrings(Symbol[] rightProd) {
        ArrayList<Symbol[]> sets = new ArrayList<Symbol[]>();

        assert(rightProd.length > 0);

        for (int i = 0; i < rightProd.length - 1; i++) {
            for (int j = i + 1; j < rightProd.length; j++) {
                sets.add(new Symbol[]{rightProd[j - 1], rightProd[j]});
            }
        }

        return sets;
    }

    private boolean contains(ArrayList<Symbol[]> set, Symbol[] pair) {
        for (Symbol[] s : set) {
            assert s.length == 2;
            assert pair.length == 2;
            if ((s[0] == pair[0]) && (s[1] == pair[1])) return true;
        }
        return false;
    }

    private void setLess(int i, int j) {
        if (precedence[i][j] == null) precedence[i][j] = "";
        if ((precedence[i][j].equals("great")) || (precedence[i][j].equals("error"))) {
            if (!precedence[i][j].equals("error")) setError(i, j, precedence[i][j] + " less");
            precedence[i][j] = "error";
        } else if ((precedence[i][j].equals("equal")) || (precedence[i][j].equals("lesseq"))) {
            precedence[i][j] = "lesseq";
        } else {
            precedence[i][j] = "less";
        }
    }

    private void setEq(int i, int j) {
        if (precedence[i][j] == null) precedence[i][j] = "";
        if ((precedence[i][j].equals("great")) || (precedence[i][j].equals("error"))) {
            if (!precedence[i][j].equals("error")) setError(i, j, precedence[i][j] + " equal");
            precedence[i][j] = "error";
        } else if ((precedence[i][j].equals("less")) || (precedence[i][j].equals("lesseq"))) {
            precedence[i][j] = "lesseq";
        } else {
            precedence[i][j] = "equal";
        }
    }


    private void setGreat(int i, int j) {
        if (precedence[i][j] == null) precedence[i][j] = "";
        if (precedence[i][j].equals("less")
                || precedence[i][j].equals("equal")
                || precedence[i][j].equals("error")) {
            if (!precedence[i][j].equals("error")) setError(i, j, precedence[i][j] + " great");
            precedence[i][j] = "error";
        } else {
            precedence[i][j] = "great";
        }
    }

    private void setError(int i, int j, String s) {
        Symbol a = grammar.getSymbolById(i);
        Symbol b = grammar.getSymbolById(j);
        if (conflicts.get(a) == null) {
            conflicts.put(a, new HashMap<Symbol, String>());
            conflicts.get(a).put(b, s);
        } else if (conflicts.get(a).get(b) == null) {
            conflicts.get(a).put(b, s);
        } else {
            if (!s.equals("error")) {
                conflicts.get(a).put(b, conflicts.get(a).get(b) + " " + s);
            }
        }
    }

    public void printRelations() {
        System.out.print("\t");
        for (int k = 0; k < precedence.length; k++) {
            System.out.print(grammar.getSymbolById(k).getName() + "\t");
        }
        System.out.println("");
        for (int i = 0; i < precedence.length; i++) {
            System.out.print(grammar.getSymbolById(i).getName() + "\t");
            for (int j = 0; j < precedence.length; j++) {
                System.out.print(precedence[i][j] + "\t");
            }
            System.out.println("");
        }
    }


    public String shift(Stack<Symbol> x, Symbol terminal) {
        assert grammar.isTerminal(terminal);
        assert !x.empty();

        if (x.peek() == grammar.getStart() && (terminal == STOP_SYMBOL)) {
            x.pop();
            if (x.peek() == STOP_SYMBOL) {
                x.push(grammar.getStart());
                return "accept";
            }
        } else if (precedence[x.peek().getId()][terminal.getId()] == null) {
            return "error";
        } else if (precedence[x.peek().getId()][terminal.getId()].equals("less")
                || precedence[x.peek().getId()][terminal.getId()].equals("equal")
                || precedence[x.peek().getId()][terminal.getId()].equals("lesseq")) {
            return "shift";
        } else if (precedence[x.peek().getId()][terminal.getId()].equals("great")) {
            return "reduce";
        } else {
            return "error";
        }
        return null;
    }

    public Production reduce(Stack<Symbol> stack, Symbol terminal) {
        Symbol[] symbols = stack.toArray(new Symbol[stack.size()]);
        Stack<Integer> lesseqPositions = new Stack<Integer>();


        assert (stack.size() >= 2);

        int i = symbols.length - 1;

        assert (stack.peek() == symbols[i]);

        while ((i > 0) && !precedence[symbols[i - 1].getId()][symbols[i].getId()].equals("less")) {
            if (precedence[symbols[i - 1].getId()][symbols[i].getId()].equals("lesseq")) {
                lesseqPositions.push(i);
            }
            i--;
        }

        assert (i > 0);
        Production res = getProduction(symbols, i);
        while(!lesseqPositions.empty() && res == null) {
            i = lesseqPositions.pop();
            res = getProduction(symbols, i);
        }

        if (res == null) {
            for (Symbol s : stack) {
                System.out.print(s.getName() + " ");
            }
            System.out.println("");
        }

        assert (res != null) : stack.peek().getName() + " " + terminal.getName() + " " + i + " " + symbols.length;
        return res;
    }

    private Production getProduction(Symbol[] symbols, int i) {
        Production[] ps = grammar.getProductions();
        label1:
        for (int k = 0; k < ps.length; k++) {
            Symbol[] right = ps[k].getRight();
            if (right.length == symbols.length - i) {
                for (int j = 0; j < right.length; j++) {
                    if (right[j] != symbols[i + j]) {
                        continue label1;
                    }
                }
                return ps[k];
            }
        }
        return null;
    }

}
